#include <iostream>
#include <random>
#include <ctime>
#include <vector>
using namespace std;
ranlux48 engine(time(nullptr));//利用时间种子生成随机数引擎

//选定一个pivot并将left到right之间的元素通过pivot划分成三部分，然后返回值等于nums[pivot]的左右两个下标
pair<int, int> _partition(vector<int> &nums, int left, int right) {
    //write ur code here.
    uniform_int_distribution<> distrib(left, right);//设置随机数范围，并为均匀分布
    int p = distrib(engine);//随机数
    int target = nums[p];
    int i = left, j = right + 1;
    p = left;
    while (p < j) { // [l,i)<t; [i,p)==t; [p,j) not visited; [j,r]>t
        if (nums[p] < target) swap(nums[i++], nums[p++]);
        else if (nums[p] == target) p++;
        else swap(nums[p], nums[--j]);
    }
    return pair<int, int>(i, j - 1);
}

void _selected_sort(vector<int> &nums, int left, int right) {
    for (int i = left; i < right; i++) {
        int idx = i;
        for (int j = i + 1; j <= right; j++) {
            if (nums[j] < nums[idx]) idx = j;
        }
        swap(nums[i], nums[idx]);
    }
}

//将nums通过_partition划分成三部分，对左右两个部分调用_quick_sort
void _quick_sort(vector<int> &nums, int left, int right) {
    //write ur code here.
    if (left >= right) return;

    bool is_sorted = true;
    for (int i = 1; is_sorted && i < nums.size();i++) {
        if (nums[i - 1] > nums[i]) is_sorted = false;
    }
    if (is_sorted) return;

    if (right < left + 3) {
        _selected_sort(nums, left, right);
        return;
    }

    pair<int, int> p = _partition(nums, left, right);
    _quick_sort(nums, left, p.first - 1);
    _quick_sort(nums, p.second + 1, right);
}

void QuickSort(vector<int> &nums) {
    _quick_sort(nums, 0, nums.size() - 1);
}

// #include "tools.h"

void print(vector<int> &ns) {
    for (int n : ns) {
        cout << n << " ";
    }
    cout << endl;
}

int main(int argc, char const *argv[]) {
    /* code */
    vector<int> nums1{ 4,3,2,2,5 };
    vector<int> nums2{ 2,2,2,2,2 };
    QuickSort(nums1);
    QuickSort(nums2);
    print(nums1);
    print(nums2);
    return 0;
}

